package 蓝桥杯_2014;

import java.util.Scanner;

/*
标题:地宫取宝
    国王有一个地宫宝库。是n * m个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。
    地宫的入口在左上角,出口在右下角。
    小明被带到地宫的入口,国王要求他只能向右或向下行走。
    走过某个格子时,如果那个格子中的宝贝价值比小明手中任意宝贝价值都大,小明就可以拿起它(当然,也可以不拿)。
    当小明走到出口时,如果他手中的宝贝恰好是 k 件,则这些宝贝就可以送给小明。
    请你帮小明算一算,在给定的局面下,他有多少种不同的行动方案能获得这k件宝贝。
【数据格式】
    输入一行3个整数,用空格分开:n m k(1<=n,m<=50,1<=k<=12)
    接下来有 n 行数据,每行有 m 个整数 Ci(0=<Ci<=12)代表这个格子上的宝物的价值
    要求输出一个整数,表示正好取k个宝贝的行动方案数。该数字可能很大,输出它对 1000007 取模的结果。
    例如,输入:
    2 2 2
    1 2
    2 1
    程序应该输出:
    2

    例如,输入:
    2 3 2
    1 2 3
    2 1 5
    程序应该输出:
    14
 */
public class Test09_地宫取宝 {

    static final int MOD = 1000007;
    static int[][] treasure;
    static int n;
    static int m;
    static int k;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        if (n < 1 || n > 50 ||m < 1 || m > 50 || k < 1 || k > 12) return;
        treasure = new int[n][m];
        // 创建地宫宝藏
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                treasure[i][j] = sc.nextInt();
                if (treasure[i][j] < 0 || treasure[i][j] > 12) return;
            }
        }
        // 递归
        long result = dfs(0, 0, -1, 0);
        System.out.println(result);
    }

    /**
     *
     * @param x     行数
     * @param y     列数
     * @param max   当前手中最大宝藏值
     * @param count 统计手中的宝藏数目 --- k
     * @return
     */
    private static long dfs(int x, int y, int max, int count) {
        // 如果超过边界 或者 手中宝藏数目大于要求的数 返回0
        if (x == n || y == m || count > k) return 0;
        // 每次移动到的位置的宝藏值
        int curr = treasure[x][y];
        // 累计方案数（取模）
        int value = 0;
        // 如果已经到达右下角
        if (x == n - 1 && y == m - 1) {
            // 并且手中宝藏数等于k 或者 包藏数=k-1，而此时最后一个的宝藏值刚好大于已拥有的，可以选择拿起
            if (count == k || (count == k - 1 && curr > max)) return 1;
        }
        // 如果当前宝藏值最大  拿---不拿
        if (curr > max) {
            // 拿起后，右移
            value += dfs(x, y + 1, curr, count + 1);
            // 拿起后，下移
            value += dfs(x + 1, y, curr, count + 1);
        }
        // 不拿，右移
        value += dfs(x, y + 1, max, count);
        // 不拿，下移
        value += dfs(x + 1, y, max, count);
        return value % MOD;
    }
}
